﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

 struct ListNode {
	int val;
	struct ListNode* next;
	ListNode(int x) : val(x), next(nullptr) {}
	
};

//将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)。
//例如：
//给出的链表为1→2→3→4→5→NULL,m = 2, n = 4,返回1→4→3→2→5→NULL.

typedef struct ListNode ListNode;

//
//class Solution {
//public:
//    ListNode* reverseBetween(ListNode* head, int m, int n) 
//    {
//        if (head == nullptr || m >= n)
//        {
//            return head;
//        }
//
//        ListNode* dummy = new ListNode(-1);//设置虚拟头结点
//        dummy->next = head;
//        ListNode* prev = dummy;
//
//        // 将 prev 指针指向第 m-1 个节点         
//        for (int i = 0; i < m - 1; i++) 
//        {
//            prev = prev->next;
//        }
//
//        ListNode* curr = prev->next; // curr 指针指向第 m 个节点
//        ListNode* tail = nullptr; // 保存第 m 个节点
//        ListNode* next = nullptr;
//
//        // 反转区间内的节点
//        for (int i = m; i <= n; i++) //从第m个节点走到第n个节点
//        {
//            next = curr->next;
//            curr->next = tail;
//            tail = curr;
//            curr = next;
//        }
//
//        // 连接反转后的区间
//        prev->next->next = curr;//连接尾部
//        prev->next = tail;//链接头部
//
//        return dummy->next;
//    }
//};


//输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
//数据范围：0≤n≤1000，−1000≤节点值≤1000
//要求：空间复杂度O(1)，时间复杂度O(n)

class Solution {
public:

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 
	{
		if (!pHead1)
		{
			return pHead2;
		}
		if (!pHead2)
		{
			return pHead1;
		}

		if (pHead1->val < pHead2->val)
		{
			pHead1->next = Merge(pHead1->next, pHead2);
			return pHead1;
		}
		else
		{
			pHead2->next = Merge(pHead1, pHead2->next);
			return pHead2;
		}
    }
};